package com.ly.algorithm.DataStructures.problem;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname Greedy
 * @Description TODO
 * @Date 2020/5/4 16:27
 * @Author 冷心影翼
 */
public class Greedy {

    private static List<List<String>> selectList = new ArrayList<>();

    public static void select(List<String> all,List<List<String>> lists) {
        while(all.size()>0) {
            int max = 0;
            List<String> maxList = lists.get(0);
            for (List<String> list : lists) {
                int count = 0;
                for(String it:all) {
                    if(list.contains(it)) {
                        count++;
                    }
                }
                if(count>max) {
                    max = count;
                    maxList = list;
                }
            }
            lists.remove(maxList);
            selectList.add(maxList);
            for(String s:maxList) {
                all.remove(s);
            }
        }

    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");
        list.add("F");
        list.add("G");

        List<String> list1 = new ArrayList<>();
        list1.add("A");
        list1.add("C");
        list1.add("D");

        List<String> list2 = new ArrayList<>();
        list2.add("C");
        list2.add("D");
        list2.add("E");

        List<String> list3 = new ArrayList<>();
        list3.add("B");
        list3.add("C");
        list3.add("D");

        List<String> list4 = new ArrayList<>();
        list4.add("E");
        list4.add("F");

        List<String> list5 = new ArrayList<>();
        list5.add("G");
        list5.add("F");



        List<List<String>> lists = new ArrayList<>();
        lists.add(list1);
        lists.add(list2);
        lists.add(list3);
        lists.add(list4);
        lists.add(list5);

        select(list,lists);
        System.out.println(selectList);
    }
}
